package sjjg.tree;

import javax.print.attribute.standard.QueuedJobCount;
import java.util.*;

public class BinaryTree<key extends Comparable<key>,value> {//二叉树
  public class Node{//树节点
     public key key;
     public value value;
     public Node left;
     public Node right;
     public Node(key key,value value,Node left,Node right){
       this.key=key;
       this.value=value;
       this.left=left;
       this.right=right;
     }
  }
  //根节点
  private Node root;
  //节点数
  private int number;

  public int getSize() {
    return number;
  }
  public void put(key key,value value){//插入节点 从树/子数(每一个不为叶子节点的节点都可看为根节点)的根开始插
    root= put(root,key,value);
  }
  public Node put(Node node, key key, value value) {//插入完成后返回新树
        if(node==null){//如果传入根节点为空的话 返回插入节点 完成插入
           number++;
           return new Node(key,value,null,null);
        }
       int compare = node.key.compareTo(key);
        //如果新节点的key<根节点key的话
        if(compare>0){
            node.left=put(node.left,key,value);//递归调用 以左子树为根节点继续寻找
          //如果新节点的key>根节点key的话
        }else if(compare<0){
           node.right=put(node.right,key,value);//递归调用 以右子树为根节点继续寻找
        }else {//如果新节点的key==根节点key的话
              node.value=value;//值替换
        }
        return node;
  }
  public Node get(key key){
        return get(root,key);
  }

  public Node get(Node root, key key) {
          if(root==null){
             return null;
          }
    int compare = root.key.compareTo(key);
          if(compare>0){// 向左寻找
             return get(root.left,key);
          }else if(compare<0){// 向右寻找
             return  get(root.right,key);
          }else {//找到了
             return  root;
          }
  }
  public void delete(key key){
        root= delete(root,key);
  }

  private Node delete(Node root, key key) {//返回删除后的新树
          if(root==null){
              return null;
          }
    int compare = root.key.compareTo(key);
          if(compare>0){
             root.left=delete(root.left,key);//递归调用
          }else if (compare<0){
             root.right=delete(root.right,key);//递归调用
          }else {//找到了
            //找到了就--
            number--;
            //特殊情况 左子树为空
            if(root.left==null){
              return root.right;
            }
            //特殊情况 右子树为空
            if(root.right==null){
               return root.left;
            }
             //找到一个节点去替代这个节点(此节点的右边的最小节点作为替代节点)
             Node minNode=root.right;
             Node preNode=null;//用来暂存替代点的前一个节点
             while (minNode.left!=null){
                   if(minNode.left.left==null){
                      preNode=minNode;
                   }
                   minNode=minNode.left;
             }//找到替代节点
             //删除替代节点的原位
             if(preNode!=null){
               preNode.left=null;
             }
             //进行替换
             minNode.left=root.left;
             minNode.right=root.right;
             root=minNode;
          }
          return root;
  }
  public key min(){
    Node min = min(root);
    if (min!=null){
       return min.key;
    }else {
       return null;
    }
  }

  public Node min(Node root) {
          if(root==null){
             return null;
          }
          if(root.left!=null){
             root= min(root.left);
          }
          return root;
  }
  public key max(){
    Node max = max(root);
    if (max!=null){
      return max.key;
    }else {
      return null;
    }
  }
  public Node max(Node root) {
    if(root==null){
      return null;
    }
    if(root.right!=null){
      root= max(root.right);
    }
    return root;
  }
  List<key>prep(){
      List<key> keys = new ArrayList<>();
      prep(root,keys);
      return keys;
  }

    private void prep(Node root, List<key> keys) {
            if(root==null){
                return;
            }
            keys.add(root.key);
            if(root.left!=null){
                prep(root.left,keys);
            }
            if(root.right!=null){
                prep(root.right,keys);
            }
    }
    List<key>midp(){
        List<key> keys = new ArrayList<>();
        midp(root,keys);
        return keys;
    }

    private void midp(Node root, List<key> keys) {
        if(root==null){
            return;
        }
        if(root.left!=null){
            midp(root.left,keys);
        }
        keys.add(root.key);
        if(root.right!=null){
            midp(root.right,keys);
        }
    }
    List<key>aftp(){
        List<key> keys = new ArrayList<>();
        aftp(root,keys);
        return keys;
    }

    private void aftp(Node root, List<key> keys) {
        if(root==null){
            return;
        }
        if(root.left!=null){
            aftp(root.left,keys);
        }
        if(root.right!=null){
            aftp(root.right,keys);
        }
        keys.add(root.key);
    }
    List<key> levp(){//层序遍历
        List<key> keys = new ArrayList<>();
        ArrayDeque<Node> anxiq = new ArrayDeque<>();
        //根节点入队
        anxiq.add(root);
        while (!anxiq.isEmpty()){
            //从队列中弹出第一个元素
            Node pop = anxiq.pop();
            keys.add(pop.key);
            //判断其左子树是否为空 不为空左子树入队
            if(pop.left!=null){
                anxiq.add(pop.left);
            }
            //判断其右子树是否为空 不为空右子树入队
            if(pop.right!=null){
                anxiq.add(pop.right);
            }
        }
        return keys;
    }
    int maxDepth(){
        return maxDepth(root);
    }

    private int maxDepth(Node root) {
          if(root==null){
              return 0;
          }
          int max=0;
          int maxL=0;
          int maxR=0;
          //递归调用查找左子树深度
        if(root.left!=null){
            maxL=maxDepth(root.left);
        }
        //递归调用查找右子树深度
        if(root.right!=null){
            maxR=maxDepth(root.right);
        }
        max=(maxL>maxR?maxL:maxR)+1;//返回较大深度加1
        return max;
    }

    public static void main(String[] args) {
    BinaryTree<Integer, String> binaryTree = new BinaryTree<>();
//    binaryTree.put(1,"张三");
//    System.out.println(binaryTree.getSize());
//    binaryTree.put(2,"李四");
//    System.out.println(binaryTree.getSize());
//    binaryTree.put(3,"王五");
//    System.out.println(binaryTree.getSize());
//    BinaryTree<Integer, String>.Node node = binaryTree.get(2);
//    System.out.println(node.value);
//    binaryTree.delete(2);
//    System.out.println(binaryTree.getSize());
//    BinaryTree<Integer, String>.Node node1 = binaryTree.get(1);
//    System.out.println(node1.value);
//      Integer min = binaryTree.min();
//      System.out.println(min);
//      System.out.println(binaryTree.max());

        binaryTree.put(5,"e");
        binaryTree.put(2,"b");
        binaryTree.put(7,"g");
        binaryTree.put(1,"a");
        binaryTree.put(4,"d");
        binaryTree.put(6,"f");
        binaryTree.put(8,"h");
        binaryTree.put(3,"c");
//        List<Integer> prep = binaryTree.levp();
//        for (Integer integer : prep) {
//            System.out.print(binaryTree.get(integer).value+" ");
//        }
        int maxDepth = binaryTree.maxDepth();
        System.out.println("最大深度:"+maxDepth);
    }
}
